/*   Copyright 2010 Jonathan Wagner
 *
 *   Licensed under the Apache License, Version 2.0 (the "License");
 *   you may not use this file except in compliance with the License.
 *   You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 */
package com.alienos.collide.uniformgrid;

import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.CopyOnWriteArrayList;

import org.javasimon.SimonManager;
import org.javasimon.Split;
import org.javasimon.Stopwatch;

import com.alienos.collide.SpatialManager;
import com.alienos.collide.SpatialObject;
import com.alienos.collide.Transform;
import com.alienos.collide.bounds.BoundingVolume;
import com.alienos.collide.event.CollisionEvent;
import com.alienos.collide.event.CollisionEvent.Type;
import com.alienos.collide.event.CollisionListener;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;

/**
 * UniformGridSpatial manager arranges SpatialObjects into 'cells', which serve
 * to prune objects that need to be tested for collisions. Collision checks only
 * need to be performed in the SpatialObject's current cell and the directly
 * adjacent cells.
 * 
 * SpatialObjects should never exceed the given cellsize for grid cells.
 * Furthermore, the cellsize can be tuned to determine the optimal size for your
 * simulation.
 * 
 * 
 * @author tigeba
 * 
 * @param <I>
 */
public class UniformGridSpatialManager<I> implements SpatialManager<I> {

    private final int gridCellSize;
    private final ConcurrentMap<UniformGridKey, UniformGridCell<I>> gridCells = new ConcurrentHashMap<UniformGridKey, UniformGridCell<I>>();
    private ConcurrentMap<I, SpatialObject<I>> spatials = new ConcurrentHashMap<I, SpatialObject<I>>();
    private CopyOnWriteArrayList<CollisionListener<I>> collisionListeners = new CopyOnWriteArrayList<CollisionListener<I>>();

    public UniformGridSpatialManager(int gridCellSize) {
        this.gridCellSize = gridCellSize;
    }

    public int totalCells() {
        return gridCells.keySet().size();
    }

    /**
     * Returns the average cell population. Useful for tuning cellsize
     * 
     * @return
     */
    public float averageCellPopulation() {

        int total = 0;
        int cells = 0;

        for (UniformGridCell<I> cell : gridCells.values()) {
            total += cell.objects().size();
            cells++;
        }

        if (cells == 0 || total == 0) {
            return 0;
        }

        return total / cells;
    }

    @Override
    public void put(I id, Transform transform, BoundingVolume bounds) {
        Stopwatch stopwatch = SimonManager.getStopwatch("UniformGridSpatialManager.put");
        Split split = stopwatch.start();
        SpatialObject<I> existing = spatials.get(id);

        if (null != existing) {
            update(existing, transform, bounds);
        } else {
            add(id, transform, bounds);
        }
        split.stop();

    }

    private void add(I id, Transform transform, BoundingVolume bounds) {
        Set<I> collisions = query(bounds, Sets.<I> newHashSet(id));

        SpatialObject<I> spatial = new SpatialObject<I>(id, transform, bounds, collisions);
        spatials.put(id, spatial);
        addToGridCell(spatial);

        collide(id, collisions);
    }

    private void update(SpatialObject<I> existing, Transform newTransform, BoundingVolume newBounds) {

        Set<I> newC = query(newBounds, Sets.<I> newHashSet(existing.getId()));
        Set<I> oldC = existing.getCollisions();

        Set<I> newCollisions = Sets.difference(newC, oldC);
        Set<I> unCollisions = Sets.difference(oldC, newC);

        SpatialObject<I> spatial = new SpatialObject<I>(existing.getId(), newTransform, newBounds, newC);

        spatials.put(existing.getId(), spatial);
        removeFromGridCell(existing);
        addToGridCell(spatial);

        if (newCollisions.size() > 0) {
            collide(existing.getId(), newCollisions);
        }

        if (unCollisions.size() > 0) {
            uncollide(existing.getId(), unCollisions);
        }

    }

    private void addToGridCell(SpatialObject<I> spatial) {
        UniformGridKey key = UniformGridKey.hash(spatial.getTransform().getPosition(), gridCellSize);
        UniformGridCell<I> cell = gridCells.get(key);

        if (null == cell) {
            cell = new UniformGridCell<I>(key);
            gridCells.put(key, cell);
        }
        cell.add(spatial);
    }

    private void removeFromGridCell(SpatialObject<I> spatial) {
        UniformGridKey key = UniformGridKey.hash(spatial.getTransform().getPosition(), gridCellSize);
        UniformGridCell<I> cell = gridCells.get(key);

        if (null == cell) {
            return;
        }
        cell.remove(spatial.getId());
    }

    private void collide(I id, Set<I> collisions) {
        // could probably wrap in a single event
        for (I collision : collisions) {
            synchronized (this) {
                SpatialObject<I> collide = spatials.get(collision);

                if (null != collide) {
                    Set<I> newCollisions = Sets.<I> newHashSet();
                    newCollisions.add(id);
                    newCollisions.addAll(collide.getCollisions());
                    spatials.put(collide.getId(),
                            new SpatialObject<I>(collide.getId(), collide.getTransform(), collide.getBounds(),
                                    newCollisions));
                }
            }
            notifyListeners(new CollisionEvent<I>(Type.Enter, id, collision));
        }
    }

    private void uncollide(I id, Set<I> uncollisions) {
        // could probably wrap in a single event
        for (I uncollide : uncollisions) {
            synchronized (this) {
                SpatialObject<I> un = spatials.get(uncollide);

                if (null != un) {
                    Set<I> newCollisions = Sets.<I> newHashSet();
                    newCollisions.addAll(un.getCollisions());
                    newCollisions.remove(id);
                    spatials.put(un.getId(), new SpatialObject<I>(un.getId(), un.getTransform(), un.getBounds(),
                            newCollisions));
                }

            }
            notifyListeners(new CollisionEvent<I>(Type.Exit, id, uncollide));
        }
    }

    @Override
    public void remove(I id) {

    }

    @Override
    public Set<I> query(BoundingVolume bounds) {
        return query(bounds, Collections.<I> emptySet());
    }

    @Override
    public Set<I> query(BoundingVolume bounds, Set<I> exclusions) {
        return query(bounds, exclusions, QueryType.Intersection);
    }

    @Override
    public Set<I> query(BoundingVolume bounds, Set<I> exclusions, com.alienos.collide.SpatialManager.QueryType queryType) {

        UniformGridKey rootKey = UniformGridKey.hash(bounds.getCenter(), gridCellSize);
        int x = rootKey.getX();
        int y = rootKey.getY();
        int z = rootKey.getZ();

        Set<I> collisions = new HashSet<I>();
        // This could possibly be optimized, but for now it checks all adjacent
        // cells
        for (int i = x - 1; i <= x + 1; i++) {
            for (int j = y - 1; j <= y + 1; j++) {
                for (int k = z - 1; k <= z + 1; k++) {
                    UniformGridCell<I> cell = getGridCell(i, j, k);
                    if (cell != null) {
                        for (SpatialObject<I> o : cell.objects()) {
                            if (queryType == QueryType.Intersection) {
                                if (bounds.intersects(o.getBounds()) && !exclusions.contains(o.getId())) {
                                    collisions.add(o.getId());
                                }
                            } else {
                                if (bounds.contains(o.getTransform().getPosition()) && !exclusions.contains(o.getId())) {
                                    collisions.add(o.getId());
                                }
                            }
                        }

                    }
                }
            }
        }
        return collisions;
    }

    private UniformGridCell<I> getGridCell(int x, int y, int z) {
        return gridCells.get(new UniformGridKey(x, y, z));
    }

    @Override
    public Transform query(I id) {
        if (spatials.containsKey(id)) {
            return spatials.get(id).getTransform();
        }
        return null;
    }

    @Override
    public void addCollisionListener(CollisionListener<I> cl) {
        if (null != cl) {
            collisionListeners.add(cl);
        }
    }

    private void notifyListeners(CollisionEvent<I> e) {
        for (CollisionListener<I> listener : collisionListeners) {
            listener.collide(e);
        }
    }

    @Override
    public String toString() {
        return "UniformGridSpatialManager [gridCellSize=" + gridCellSize + ", totalCells()=" + totalCells()
                + ", averageCellPopulation()=" + averageCellPopulation() + "]";
    }

    @Override
    public Set<I> getManagedObjects() {
        return ImmutableSet.copyOf(spatials.keySet());
    }

}
